package offer.offer01;

/**
 * todo: 题解里有取余一些数学知识。
 */
public class S14II剪绳子 {
    /**
     * 100，剪绳子的结果只能是3, 2, 因为任何一个大于3的数, 给他剪出来一个2都会变大, 所以只能出现2, 3, 然后应该是一堆3一个或没有2
     * 有几个注意: 首先必须剪, 然后是因为取模，虽然因为最大1000000007 * 3， 所以也不会碰到MAX_VALUE。
     */
    public int cuttingRope(int n) {
        if(n == 2) return 1;
        if(n == 3) return 2;
        // 用long保护一下输出防止溢出
        long res = 1;
        int triNum = n / 3;
        int douNum = n % 3;
        switch (douNum){
            case 0:
                break;
            case 1:
                triNum --;
                douNum = 2;
                break;
            case 2:
                douNum = 1;
                break;
        }
        // 注意无处不在的取余操作。
        // 注意这里是先算完triNum > 0 这个操作, 再执行的triNum--, 所以如果truNum=1, 是可以执行一次的.
        while(triNum -- > 0){
            res = (res * 3) % 1000000007;
        }
        while(douNum -- > 0){
            res = (res * 2) % 1000000007;
        }
        return (int) res;
    }

    /**
     * 体面
     */
    public int cuttingRope2(int n) {
        if(n <= 3) return n - 1;
        long res=1L;
        int p=(int)1e9+7;
        //贪心算法，优先切三，其次切二
        while(n>4){
            res=res*3%p;
            n-=3;
        }
        //出来循环只有三种情况，分别是n=2、3、4
        return (int)(res*n%p);
    }
}
